package com.peng.leetcode.tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * LowestCommonAncestor1
 * 236. 二叉树的最近公共祖先
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 *
 * <p>
 * Created on 2022/11/21
 *
 * @author lupeng
 */
public class LowestCommonAncestor1 {

    private Map<TreeNode, TreeNode> node2ParentMap = new HashMap<>();

    private Set<TreeNode> visited = new HashSet<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p);
            p = node2ParentMap.get(p);
        }
        while (q != null) {
            if (visited.contains(q)) {
                return q;
            }
            q = node2ParentMap.get(q);
        }
        return null;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            node2ParentMap.put(root.left, root);
            dfs(root.left);
        }
        if (root.right != null) {
            node2ParentMap.put(root.right, root);
            dfs(root.right);
        }
    }

}
